package src.UF;

/**
 * 并查集
 * 数组实现
 * Quick Find
 */
public class QuickFind implements UF {

    private int[] ids;

    public QuickFind(int size){
        ids  = new int[size];
        for (int i = 0; i < ids.length; i++) {
            ids[i] = i;
        }
    }


    @Override
    public int getSize() {
        return ids.length;
    }
    
    private int find(int p){
        if (p < 0 || p >=ids.length) {
            throw new IllegalArgumentException("index out of range.");
        }
        return ids[p];
    }
    
    /**
     * 查看元素p q是否连接
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
    /**
     * 连接元素p q
     */
    @Override
    public void unionElements(int p, int q) {
        int pId = find(p);
        int qId = find(q);
        if (pId == qId) {
            return ;
        }
        for (int i = 0; i < ids.length; i++) {
            if (ids[i] == pId) {
                ids[i] = qId;
            }
        }
    }

}